package leetcode.binaryTree;

import java.util.List;

public interface SolutionService {

	//108.Convert Sorted Array to Binary Search Tree
	TreeNode sortedArrayToBST(int[] nums);
	
	//100.Same Tree
	boolean isSameTree(TreeNode p, TreeNode q);
	
	//101.Symmetric Tree
	//http://blog.csdn.net/derrantcm/article/details/47333335
	boolean isSymmetric(TreeNode root);
	
	//104.Maximum Depth of Binary Tree
	int maxDepth(TreeNode root);
	
	//107.Binary Tree Level Order Traversal II
	List<List<Integer>> levelOrderBottom(TreeNode root);
	
	//110.Balanced Binary Tree
	boolean isBalanced(TreeNode root);
	
	//111.Minimum Depth of Binary Tree
	int minDepth(TreeNode root);
	
	//112.Path Sum
	boolean hasPathSum(TreeNode root, int sum);

	//235. Lowest Common Ancestor of a Binary Search Tree
	// https://www.cnblogs.com/grandyang/p/4640572.html
	TreeNode lowestCommonAncestorBST(TreeNode root, TreeNode p, TreeNode q);


	/**
	 * 236. Lowest Common Ancestor of a Binary Tree
	 * https://www.cnblogs.com/rainbow-/p/10388173.html
	 * 以某个节点为根结点,
	 * 如果两个问题节点分别在此根结点的左右两侧 或其中一个问题节点与这个节点相等,那么这个节点就是解.
	 * 如果两个问题节点都分布在根结点的一端,那么这个节点就不是解,但是这一端中包含着问题的解,而另一端则不含解
	 * @param root
	 * @param p
	 * @param q
	 * @return
	 */
	TreeNode lowestCommonAncestorBT(TreeNode root, TreeNode p, TreeNode q);

	/**
	 * 404. Sum of Left Leaves
	 * https://leetcode.com/problems/sum-of-left-leaves/
	 * @param root
	 * @return
	 */
	int sumOfLeftLeaves(TreeNode root);
	
}
